
package unbounded_lockfree_queue;

import java.util.concurrent.atomic.AtomicReference;

public class LockFreeQueue<T> {
  AtomicReference<Node<T>> head, tail;
  
  public LockFreeQueue () {
    Node<T> node = new Node<T>(null);
    head.set(node);
    tail.set(node);
  }
  
  public void enq (T value) {
    Node<T> node = new Node<T>(value);
    while(true) {
      Node<T> last = tail.get();
      Node<T> next = last.next.get();
      if (last == tail.get()) {
        if (next == null) {
          if (last.next.compareAndSet(next, node)) {
            tail.compareAndSet(last, node);
            return;
          }
        } else {
          tail.compareAndSet(last, next);
        }
      }
    }
  }
  
  public T deq() throws EmptyException {
    while (true) {
      Node<T> first = head.get();
      Node<T> last = tail.get();
      Node<T> next = first.next.get();
      if (first == head.get()) {
        if (first == last) {
          if (next == null)
            throw new EmptyException();
          tail.compareAndSet(last, next);
        } else {
          T value = next.value;
          if (head.compareAndSet(first, next))
            return value;
        }
      }
    }
  }
}